package problems;

import java.util.HashMap;
import java.util.Map;

public class Euler074 extends AbstractEuler {

	//the keys of this map are numbers that are part of a loop;
	//the values are the number of numbers in that loop.
	private static final Map<Integer, Integer> loops = new HashMap<Integer, Integer>();
	static {
		loops.put(169, 3);
			loops.put(363601, 3);
				loops.put(1454, 3); //loop 1
				
		loops.put(871, 2);
			loops.put(45361, 2); //loop 2
			
		loops.put(872, 2);
			loops.put(45362, 2); //loop 3
		
	}
	
	@Override
	public Number calculate() {
		//since the starting number must be below 1000000,
		//the upper bound for number in a chain is 7*9! = 2540160, and quite probably lower.
		
		int answer = 0;
		
		startingNumber:
		for (int i = 1; i < 1000000; i++) {
			
			int next = i;

			for (int chainLength = 1; chainLength < 60; chainLength++) { //60 is the chain length asked for in the problem
				int old = next;
				next = getNextInChain(next);

				if (next == i) { //back at starting number before reaching length 60
					continue startingNumber;
				}
				
				if (old == next) { //self-referential loop
					continue startingNumber;
				}
				
				Integer endLoop = loops.get(next); //previously defined loops
				if (endLoop != null) {
					if (chainLength + endLoop == 60) {
						answer++;
					} else {
						continue startingNumber;
					}
				}
				
			}
			
			//didn't pop out of the loop, so length must be 60
			assertEquals("expected to be back at start", i, next);
			answer++;
	
		}
		
		return answer;
	}
	
	public void testNextTerm() {
		assertEquals(145, getNextInChain(145));
		assertEquals(2177280, getNextInChain(999999));
		assertEquals(1454, getNextInChain(363601 ));
		assertEquals(872, getNextInChain(getNextInChain(872)));
	}

	@Override
	protected Number getCorrectAnswer() {
		return 402;
	}
	
	private int getNextInChain(int input) {
			int next = 0;
			while (input > 0) {
				//this is the inner loop so the most performance can be gained here;
				//given the limited set of factorials we will need, there is no need
				//to calculate them. Instead, hard-code each digit.
				switch(input % 10) { //LSD
					case 0: next += 1;		break;
					case 1: next += 1;		break;
					case 2: next += 2;		break;
					case 3: next += 6;		break;
					case 4: next += 24;		break;
					case 5: next += 120;	break;
					case 6: next += 720;	break;
					case 7: next += 5040;	break;
					case 8: next += 40320;	break;
					case 9: next += 362880; break;
				}
				input /= 10; //chop off LSD
			}
			return next;

	}

}
